﻿/// <summary>
/// https://leetcode-cn.com/problems/trapping-rain-water/
/// </summary>
public class Solution
{
    public int Trap(int[] height)
    {
        if (height.Length < 3)
            return 0;

        var leftMax = height[0];
        var rightMax = height[2..].Max();

        var result = 0;
        for (int i = 1; i < height.Length - 1; i++)
        {
            var current = height[i];
            var min = Math.Min(leftMax, rightMax);
            result += Math.Max(0, min - current);

            leftMax = Math.Max(leftMax, current);
            if (current == rightMax)
                rightMax = height[(i + 1)..].Max();
        }
        return result;
    }
}

/* 下方案超时
/// <summary>
/// https://leetcode-cn.com/problems/trapping-rain-water/
/// </summary>
public class Solution
{
    public int Trap(int[] height)
    {
        var result = 0;
        for(int i = 1; i < height.Length - 1; i++)
        {
            var left = height.Take(i).Max();
            var right = height.Skip(i).Max();
            var min = Math.Min(left, right);
            result += Math.Max(0, min - height[i]);
        }
        return result;
    }
}
*/